package searchStudy;

public class SingleNodDuplicate {

    /**
     * LeetCode T540 有序数组中的单一元素
     *
     * 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2,3,3,4,4,8,8};
        singleNonDuplicate(nums);
    }

    public static int singleNonDuplicate(int[] nums) {
        int len = nums.length;
        int low = 0;
        int high = len - 1;
        while (low <= high){
            int mid = (low + high) >> 1;
            //如果mid是偶数
            if (mid%2 == 0){
                //前面的值存在且与中间值相等，需要求的值在左边
                if (mid-1 >= 0 && nums[mid-1] == nums[mid]){
                    high = mid - 2;
                } else if ( mid + 1 < len && nums[mid + 1] == nums[mid]){ //后面的值存在且与中间值相等
                    low = mid + 2;
                } else { //上面两种条件均不满足，则返回
                    return nums[mid];
                }
            } else { //如果mid是奇数
                if (mid-1>=0 && nums[mid-1]==nums[mid]){
                    low = mid + 1;
                } else if ( mid + 1 < len && nums[mid + 1] == nums[mid]){ //后面的值存在且与中间值相等
                    high = mid - 1;
                } else { //上面两种条件均不满足，则返回
                    return nums[mid];
                }
            }
        }
        return 0;
    }
}
